COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00013 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a55.tex[154,phy] \today\hfill}

\parskip 5pt
\bigskip

\line{\bf Final Exam -- Part I. Closed book. Autumn 1984\hfill}
\medskip
\line{\bf True or False. (16 points.)\hfill}

\medskip
\disleft 40pt:\phantom{0}1. \hrulefill:
Is $\{a↑ib↑jc↑id↑j\}$ a CFL?

\disleft 40pt:\phantom{0}2. \hrulefill:
Is $\{a↑ib↑ic↑i\}$ the intersection of two CFLs?

\disleft 40pt:\phantom{0}3. \hrulefill:
Is it the union of two CFLs?

\disleft 40pt:\phantom{0}4. \hrulefill:
If $L$ is the complement of a CFL, it is recursive.

\disleft 40pt:\phantom{0}5. \hrulefill:
The image of a recursive language under a gsm mapping is recursive.

\disleft 40pt:\phantom{0}6. \hrulefill:
If $L$ is a FAL, there is an algorithm to test two strings for infix
equivalence, $x\Lap y$.

\disleft 40pt:\phantom{0}7. \hrulefill:
If an $n$-state D1CM makes more than $n$ steps without reading, it is in
an infinite loop.

\disleft 40pt:\phantom{0}8. \hrulefill:
In a CFL, every sufficiently long string is of the form $uvwxyz$, where
$|vxz|≥1$, and $\{uv↑iwx↑iyz↑i\}$ is a subset of the language.

\disleft 40pt:\phantom{0}9. \hrulefill:
The language of strings accepted by a Turing machine is recursive.

\disleft 40pt:10. \hrulefill:
A DPDA can accept a language not accepted by any N1CM.

\disleft 40pt:11. \hrulefill:
A N1CM can accept a language not accepted by any DPDA.

\disleft 40pt:12. \hrulefill:
There is an algorithm to decide whether two regular expressions define the
same language.

\disleft 40pt:13. \hrulefill:
If $L$ is accepted by a D1CM, it is accepted by one that halts on all inputs.

\disleft 40pt:14. \hrulefill:
There is an algorithm to decide if two CFGs define the same language.

\disleft 40pt:15. \hrulefill:
The set of ambiguous CFGs is recursively enumerable.

\disleft 40pt:16. \hrulefill:
If $M↓1$ and $M↓2$ are NPDTs, there is another, $M↓3$, such that
$IO↓{M↓1}\circ IO↓{M↓2}=IO↓{M↓3}$.

\vfill\eject

\line{\bf Final Exam -- Part II. Open book. Autumn 1984\hfill}

{\sl Prove\/} all your answers; ``plausible'' arguments will not count.
Theorems from Hopcroft and Ullman or from the course notes may be cited,
provided that there are complete proofs in the places cited. That is,
don't just quote something an authority figure said but didn't prove.

You are not expected to solve, or even try to solve, all questions. Aim
for {\sl good\/} proofs on at least two, and preferably three.

{\sl Please\/} write large and clearly, in ink. Use a separate blue book for
each problem.

\medskip
\line{\bf Definitions:\hfill}

$L↓{(\,)}$ is defined by the grammar:
$$S→\epsilon\mid (S)S\,.$$
You may take as given that prefixes have at least as many ``('' and ``)'',
and suffixes conversely.

$L↓{(\,)[\,]}$ is defined by
$$S→\epsilon\mid (S)S\mid [S]S\,.$$
This is the language of nested parentheses of two types; it includes 
$\bigl(\,(\,)\,[\,(\,)\,]\,\bigr)$
but not $(\,[\,]$ nor $(\,[\,]\,]$. Again you may assume its obvious properties.

If $x=x↓1x↓2\ldots x↓n$ and $y=y↓1y↓2\ldots y↓n$ are strings,
$x↓i\in\Sigma↑{\ast}$, $y↓i\in\Sigma↑{\ast}$, then
$x↓1y↓1x↓2y↓2\ldots x↓ny↓n$ is a {\sl shuffle\/} of~$x$ and~$y$. If $L↓1$
and~$L↓2$ are languages, ${\rm shuffle}(L↓1,L↓2)$ is the set $\{\,z\mid z$
is a shuffle of some $x\in L↓1$ and some $y\in L↓2\,\}$. You may use the
obvious properties of the shuffle operator.

\bigskip
\line{{\bf Problem 1.} [5 points.]\hfill}

If $L=1↑{\ast}0\bigl((0+1)(0+1)\bigr)↑{\ast}$, how many equivalence classes
does $\zap$ have? Give a regular expression for each. Give a minimized FA
for~$L$. (No proofs required.)

\medskip
\line{{\bf Problem 2.} [5 points.]\hfill}

Let $L$ be the set of strings over $\{A,B\}$ containing $ABA$. How would
you determine if $x\zzap y$?

\medskip
\line{{\bf Problem 3.} [5 points.]\hfill}

If $L$ is a FAL of $n$ states, and $x=x↓1x↓2\ldots x↓k\in L$, $k≥n$,
$x↓i\in\Sigma↑+$, then a contiguous subset of the $x↓i$'s can be omitted
to get another string in~$L$. Is the analogous statement true of CFLs?

\medskip
\line{{\bf Problem 4.} [10 points.]\hfill}

Prove that the set of strings of the form $x+y=z$, where $x$ and $y$ are
decimal integers greater than zero, and where the formula is true, is 
not a~CFL.

\medskip
\line{{\bf Problem 5.} [25 points.]\hfill}

\disleft 25pt:{\bf (A)}:
[5 points.]\xskip 
Is ${\rm shuffle}(b↑{\ast},\{a↑ib↑ic↑i\})$ a CFL?

\disleft 25pt:{\bf (B)}:
[10 points.]\xskip 
Is ${\rm shuffle}(a↑{\ast}b↑{\ast}c↑{\ast}d,a↑ib↑ic↑i)$ a CFL?

\disleft 25pt:{\bf (C)}:
[10 points.]\xskip 
Is ${\rm shuffle}(a↑{\ast}b↑{\ast}c↑{\ast},a↑ib↑ic↑i)$ a CFL?

\medskip
\line{{\bf Problem 6.} [25 points.]\hfill}

If $L↓1$ is a CFL with unambiguous grammar $G$, and $L↓2$ the language
accepted by DFA~$M$:

\disleft 25pt:{\bf (A)}:
[5 points.]\xskip
Is there necessarily an unambiguous grammar for $L↓1\cap L↓2$?

\disleft 25pt:{\bf (B)}:
[10 points.]\xskip
Is there necessarily an unambiguous grammar for $L↓1\cup L↓2$?

\disleft 25pt:{\bf (C)}:
[10 points.]\xskip
Is there necessarily an unambiguous grammar for ${\rm shuffle}(L↓1,L↓2)$?

\disleft 25pt::
(This comes up in practice when $L↓1$ is a programming language without
comments and $L↓2$ is a language of comments that can be ``shuffled'' in,
somewhat analogously to Pascal.)

\medskip
\line{{\bf Problem 7.} [5 points.]\hfill}

It was shown in a handout that $L↓1=\{a↑ib↑ic↑j\}\cup \{a↑ib↑jc↑j\}$
is inherently ambiguous. What about $L↓2=\{a↑ib↑ia↑j\}\cup\{a↑ib↑ja↑j\}$?

\medskip
\line{{\bf Problem 8.} [10 points.]\hfill}

Prove:

\disleft 25pt::
[5 points.]\xskip
If $L$ is the image of $L↓{(\,)}$ under a gsm mapping, then $L$ is accepted
by a N1CM.

\disleft 25pt::
[5 points.]\xskip
If $L$ is the image of $L↓{(\,)[\,]}$ under a gsm mapping, then $L$ is accepted
by a NPDA.

\medskip
\line{{\bf Problem 9.} [10 points.]\hfill}

An $n$-state D1CM reads $a↑mb$. Just before reading the $b$, show that the
value of the counter is either $≤n$ or $≥m/n$.

\medskip
\line{{\bf Problem 10.} [10 points.]\hfill}

Show that there is a recursive language $L$, such that every recursively
enumerable language is the image of~$L$ under some dgsm mapping.
(I.e., every r.e.~language is $L\circ IO↓M$ for some dgsm~$M$.)


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
Autumn 1984.
%revised date;
%subsequently revised.

\bye